package com.markus.code.二叉树.leetcode;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/12 22:41
 * todo: 二叉树的直径
 */
public class LeetCode_543 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public static class Info{
        public int maxLength;
        public int currDepth;
        public Info(int maxLength,int currDepth){
            this.maxLength = maxLength;
            this.currDepth = currDepth;
        }
    }
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null){
            return 0;
        }
        return process(root).maxLength;
    }
    private Info process(TreeNode x){
        if (x == null){
            return new Info(0,0);
        }
        Info left = process(x.left);
        Info right = process(x.right);
        int maxLength = 0;
        int currDepth = Math.max(left.currDepth,right.currDepth)+1;
        //与x无关
        maxLength = Math.max(left.maxLength,right.maxLength);
        //与x有关
        maxLength = Math.max(left.currDepth+right.currDepth+1,maxLength);
        return new Info(maxLength,currDepth);
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        A.left = new TreeNode(2);
        A.right = new TreeNode(3);
        A.left.left = new TreeNode(4);
        A.left.right = new TreeNode(5);
        LeetCode_543 demo = new LeetCode_543();
        int i = demo.diameterOfBinaryTree(A);
        System.out.println(i);
    }
}
